function WayToSwap(piece, index) {
  this.piece = piece;
  this.index = index;
  this.succeeded = false;
  this.ACTION_SPLIT = "split";
  this.ACTION_MERGE = "merge";
  this.action = this.ACTION_SPLIT;
  this.direction = UNKNOWN_DIR;
  this.side = UNKNOWN_SIDE;
  this.sources = new Array();  // one if split, many if merge
  this.value = 0;
  this.swapStart = null;
  this.destination = null;
}

function Estimate(value, sources, pieceToSwap, side) {
  this.value = value;
  this.sources = sources;
  this.swapStart = pieceToSwap;
  if (sources && sources.length == 4) {
    this.side = side;
  }
}

Estimate.prototype.isValid = function() {
  return this.sources && this.sources.length > 0 && this.swapStart;
}

function Link(side, id, splitDir) {
  this.side = side;
  this.id = -1;
  if (id != undefined) {
    this.id = id;
  }
  this.splitDir = UNKNOWN_DIR;
  this.mergeSide = UNKNOWN_SIDE;
  if (splitDir != undefined) {
    this.splitDir = splitDir;
  }
}

Link.prototype.isValid = function() {
  return this.id >= 0;
}




function Algorithm() {
  this.PIECE_VALUE_THRESHOLD = 0.8;
  this.PIECE_VALUE_MAX = 15;
  this.color = NULL_COLOR;
}




Algorithm.prototype.makeMove = function(move) {
  this.color = move.color;
  var importantPieces = this._getOpponentsImportantPieces(move.board);

  var numPiecesToConsider = this._getNumberOfPiecesToConsider(importantPieces);
  /*if (numPiecesToConsider < 5) {
    numPiecesToConsider = 5;
  }
  */
  if (importantPieces.length < numPiecesToConsider) {
    numPiecesToConsider = importantPieces.length;
  }
  var ways = new Array();
  var enoughWays = false;
  var k = 0;
  var backupWay= null;
  while (! enoughWays && k < importantPieces.length) {
    var way = this._getWayToSwapPiece(move.board, importantPieces[k], k);
    if (way.succeeded) {
      if (backupWay == null) {
        backupWay = way;
      }
      ways.push(way);
    }
    if (ways.length < numPiecesToConsider) {
      k += 1;
    } else {
      enoughWays = true;
    }
  }
  var foundAtLeastOneGoodMove = false;
  while (!foundAtLeastOneGoodMove && k < importantPieces.length-1) {
    ways = this._reevaluateWays(ways, move);
    if (ways.length == 0) {
      // oh-oh - cumble mate?!
      k+=1;
      var way = this._getWayToSwapPiece(move.board, importantPieces[k], k);
      if (way.succeeded) {
        ways.push(way);
      }
    } else {
      foundAtLeastOneGoodMove = true;
    }
  }
  if (!foundAtLeastOneGoodMove) {
    ways = [backupWay];
  }

  ways.sort(Algorithm.prototype._byValue);
  var topValue = ways[0].value;
  var i = 1;
  while (i < ways.length && topValue * 0.8 < ways[i].value) {
    i+=1;
  }
  var j = Math.floor(Math.random() * i);
  if (j > 0) {
    var temp = ways[0];
    ways[0] = ways[j];
    ways[j] = temp;
  }

  for (var i = 0; i < ways.length; i++) {
      var way = ways[i];
      if (way.succeeded) {
	      var succeeded = this._tryToUpdateMove(way, move);
	      if (succeeded) {
			if (!foundAtLeastOneGoodMove) {
		      move.message = "Looks like " + COLOR_TEXT[move.color] + " is crumble mated!";
			}
	        return;
	      } else {
	        move.reset();
            move.message = "The piece was captured during swap, trying alternative " + (i + 1);
	      }
      }
   }
}

Algorithm.prototype.cloneCallback = function(from, to) {
    if (from.alg_link) {
        to.alg_link = [];
	    for (var i = 0; i < from.alg_link.length; i++) {
	      if (from.alg_link[i]) {
		      to.alg_link[i] = new Link(from.alg_link[i].side,
		         from.alg_link[i].id, from.alg_link[i].splitDir);
		      to.alg_link[i].mergeSide = from.alg_link[i].mergeSide;
          }
	    }
	 }
}


Algorithm.prototype._tryToUpdateMove = function (way, move) {
  var board = move.board;
  assert(way.succeeded);
  var longSplitCandidates = [[],[]];
  var finalSplitPieces = [];
  move.setDemoMode(true);
  var startPiece = null;
  if (way.action == way.ACTION_SPLIT) {
    assert(way.sources.length > 0);
    if (way.sources.length == 2) {
      move.longSplit(board.equivalent(way.sources[0]),
                     board.equivalent(way.sources[1]),
                     way.direction);
    } else {
      assert(way.sources.length == 1);
      var piece = board.equivalent(way.sources[0]);
      longSplitCandidates = board.getAllAvailableLongSplitCandidates(piece, way.direction);
      finalSplitPieces = move.split(piece, way.direction);
    }
    startPiece = board.equivalent(way.swapStart);
    this._createLinkAndAjust(board, startPiece, way.sources[0], way.index);
  } else { // merge
    assert(way.sources.length == 4);
    move.merge(board.equivalent(way.sources[0]),
    				board.equivalent(way.sources[1]),
    				board.equivalent(way.sources[2]),
    				board.equivalent(way.sources[3]));
    startPiece = board.equivalent(way.swapStart);
    this._createLinkAndAjustForMerge(board, startPiece, way.side, way.index);
  }
  var destination = board.equivalent(way.destination);
  var swappedPieces = this._findSwappingSequence(startPiece, destination, way.index);
  if (way.action == way.ACTION_SPLIT) {
    var piecesForLongSplit = this._findPiecesForLongSplit(longSplitCandidates, swappedPieces.length, new Rational(move.board.x, 1));
    for (var p = 0; p < piecesForLongSplit.length; p++) {
      move.split(piecesForLongSplit[p], way.direction);
    }
  }

  assert(swappedPieces[0] == startPiece);
  var succeeded = true;
  for (var s = 0; s < swappedPieces.length; s++) {
    if (!move.swap(swappedPieces[s], UNKNOWN_SIDE)) {
      succeeded = false;
      break;
    }
  }
  if (succeeded) {
    assert(swappedPieces[swappedPieces.length-1] == destination); // last one
    move.setDemoMode(false);
    return true;
  } else {
    return false;
  }
}

Algorithm.prototype._getNumberOfPiecesToConsider = function(importantPieces) {
  var numPiecesToConsider = 1;
  var topValue = importantPieces[0].value;
  while (numPiecesToConsider < importantPieces.length && topValue * this.PIECE_VALUE_THRESHOLD < importantPieces[numPiecesToConsider].value) {
    numPiecesToConsider +=1;
  }
  if (numPiecesToConsider > this.PIECE_VALUE_MAX) {
    numPiecesToConsider = this.PIECE_VALUE_MAX;
  }
  return numPiecesToConsider;
}

Algorithm.prototype._findPiecesForLongSplit = function(candidates, swappedSequenceLength, boardLength) {
  var all = [];

  var end = [ZERO, ZERO];
  var start = [boardLength, boardLength];
  for (var i = 0; i < 2; i++) {
    for (var k = 0; k < candidates[i].length; k++) {
      for (var dir = 0; dir < 2; dir++) {
        if (candidates[i][k].start[dir].smaller(start[dir])) {
          start[dir] = candidates[i][k].start[dir];
        }
        if (candidates[i][k].end[dir].bigger(end[dir])) {
          end[dir] = candidates[i][k].end[dir];
        }
      }
    }
  }
  // if the length of the split > half of the board, do the whole thing
  if (end[HORIZONTAL].subtract(start[HORIZONTAL]).twice().bigger(boardLength) ||
      end[VERTICAL].subtract(start[VERTICAL]).twice().bigger(boardLength))
  {
    for (var i = 0; i < 2; i++) {
       for (var k = 0; k < candidates[i].length; k++) {
         all.push(candidates[i][k]);
       }
     }
     return all;
  }

  // find the length of split
  if (swappedSequenceLength > 3) {
    if (candidates[0].length > 0) {
      return [candidates[0][0]]; // renewable
    } else if (candidates[1].length > 0) {
      return [candidates[1][0]];
    }
  }
  for (var i = 0; i < 2; i++) {
    var j = Math.ceil(Math.random()*candidates[i].length);
    for (var k = 0; k < j; k++) {
      all.push(candidates[i][k]);
    }
  }
  return all;
}

// protected
Algorithm.prototype._reevaluateWays = function(ways, move) {
  return ways;
}

Algorithm.prototype._getOpponentsImportantPieces = function(board) {
  var important = new Array();
  this._evaluate(board, this.color);
  board.pieces.sort(Algorithm.prototype._byValue);
  for (var i = 0; i < board.pieces.length; i++) {
    if (board.pieces[i].value > 0) {
      important.push(board.pieces[i]);
    }
  }
  return important;
}

Algorithm.prototype._byValue = function(a,b) {
  return b.value - a.value;
}

Algorithm.prototype._evaluate = function(board, mycolor) {
  var score = 0.0;
  var globalMyLinks = [0,0,0,0,0];
  var globalOpponentLinks = [0,0,0,0,0];
  board.evaluate();
  for (var i = 0; i < board.pieces.length; i++) {
    if (board.pieces[i].color != mycolor) {
      globalOpponentLinks[board.pieces[i].numLinksToBorders]+=1;
      var linkToBorder = [0, 0, 0, 0];
      var myNeighborMaxNumLinksToBorders = 0;
      for (var side = 0; side < 4; side ++) {
        for (var c = 0; c < board.pieces[i].connections[side].length; c++) {
          var n = board.pieces[i].connections[side][c];
          if (n.color == mycolor) { // my pieces
	          if (n.numLinksToBorders > myNeighborMaxNumLinksToBorders) {
	            myNeighborMaxNumLinksToBorders = n.numLinksToBorders;
	          }
	          for (var l = 0; l < 4; l++) {
	            if (linkToBorder[l] == 0 && n.linkToBorder[l]) {
	              linkToBorder[l] = 1;
	            }
	          }
          }
        }
      }
      var myNumOfPotentialLinks = 0;
      for (var l = 0; l < 4; l++) {
        myNumOfPotentialLinks += linkToBorder[l];
      }
      /*
      // now see how many opponents links to borders we break by swapping this piece
      var b = board.clone();
      var p = b.equivalent(board.pieces[i]);
      p.swap();
      b.evaluate();
      var opponentNeighborMaxNumLinksToBorders = 0;
      for (var side = 0; side < 4; side ++) {
        for (var c = 0; c < p.connections[side].length; c++) {
          var n = p.connections[side][c];
          if (n.color != mycolor) { // my pieces
	          if (n.numLinksToBorders > opponentNeighborMaxNumLinksToBorders) {
	            opponentNeighborMaxNumLinksToBorders = n.numLinksToBorders;
	          }
          }
        }
      }
      */

      // todo - write better alg
      board.pieces[i].value = 10000 * (myNumOfPotentialLinks - myNeighborMaxNumLinksToBorders) + 100.0 * myNumOfPotentialLinks + board.pieces[i].numLinksToBorders*10 + board.pieces[i].x.float() * board.pieces[i].y.float();
    } else {
      globalMyLinks[board.pieces[i].numLinksToBorders]+=1;
      board.pieces[i].value = 0.0;
    }
  }
  score = globalMyLinks[4] * 10000000 + globalMyLinks[3] * 1000 + globalMyLinks[2] * 10 + globalMyLinks[1] -
          globalOpponentLinks[4] * 10000000 - globalOpponentLinks[3] * 1000 - globalOpponentLinks[2] * 10 - globalOpponentLinks[1] ;
  return score;
}

Algorithm.prototype._evaluateFast = function(board, mycolor) {
  return this._evaluate(board, mycolor);
}

Algorithm.prototype._getWayToSwapPiece = function(thisboard, piece, index) {
  var way = new WayToSwap(piece, index);
  assert(piece.color != this.color);
  var sources = this._findAllSourcesForSwap(thisboard, piece, index); //<--
  if (sources.length == 0) {
    return way; // unsuccessful;
  }
  var bestEstimate = new Estimate(-1000000000, null, null);
  for (var i = 0; i < sources.length; i++) {
    // support only split for now
    var board = thisboard.clone();
    var s = sources[i];
    s.used = true;
    var myPiece = board.equivalent(piece);
    var mySource = board.equivalent(s);
    var link = s.alg_link[index];
    var swapStart = null;
    var srcs = [];
    if (link.splitDir != UNKNOWN_DIR) {
	  var splitPieces = board.split(mySource, link.splitDir);
   	  swapStart = splitPieces[1];
      if (board.aligned(splitPieces[0], s.connections[link.side][link.id])) {
        swapStart = splitPieces[0];
      }
      srcs = [s];
    } else {
      assert(link.mergeSide != UNKNOWN_SIDE);
      srcs = Algorithm.prototype._generateSourcesForMerge(mySource, link.mergeSide);
      var mergedPieces = board.merge(srcs[0], srcs[1], srcs[2], srcs[3]);
      swapStart = mergedPieces[0]; // there is only 1 element, yeah
      assert(swapStart);
    }
    swapStart.swap();
    myPiece.swap();
    var estimate = new Estimate(this._evaluateFast(board, this.color), srcs, swapStart, link.side);
	myPiece.swap(); // swap back
	if (estimate.value > bestEstimate.value) {
      var swappedPieces = this._findSwappingSequence(s, piece, index);
      var swapSucceeded = true;
   	  for (var j = 1; j < swappedPieces.length; j++) {
	    var next = board.equivalent(swappedPieces[j]);
	    next.swap();
	    if (board.isPieceCaptured(next, OPPOSITE_COLOR[next.color])) {
	        swapSucceeded = false;
	        break;
	    }
	    next.swap();
	  }
      if (swapSucceeded) {
        bestEstimate = estimate;
      }
    }
  }
  if (!bestEstimate.isValid()) {
    return way;
  }
  way.succeeded = true;
  way.sources = bestEstimate.sources;
  way.side = bestEstimate.side;
  if (bestEstimate.sources.length == 1) {
    way.action = way.ACTION_SPLIT;
    way.direction = bestEstimate.sources[0].alg_link[index].splitDir;
  } else {
    way.action = way.ACTION_MERGE;
    way.sources = bestEstimate.sources;
  }
  way.swapStart = bestEstimate.swapStart;
  way.value = bestEstimate.value;
  way.destination = piece;
  return way;
}


Algorithm.prototype._findAllSourcesForSwap = function(board, piece, index) {
  var neighbors = new Array();
  this._findAllAlignedSwappablePiecesRec(board, piece, piece.color, index, neighbors);
  var potentials = new Array();
  for (var n = 0; n < neighbors.length; n++) {
    neighbors[n].alg_alignedMarked = false;
    var myPotentials = this._findImmediateSourcesToMerge(board, neighbors[n], index);
    for (var i = 0; i < myPotentials.length; i++) {
      potentials.push(myPotentials[i]);
    }
    var myPotentials= this._findImmediateSourcesToSplit(board, neighbors[n], index);
    for (var i = 0; i < myPotentials.length; i++) {
      potentials.push(myPotentials[i]);
    }
  }
  return potentials;
}


Algorithm.prototype._findAllAlignedSwappablePiecesRec = function(board, piece, color, index, out) {
  piece.alg_alignedMarked = true;
  out.push(piece);
  for (var side = 0; side < 4; side++) {
    for (var i = 0; i < piece.connections[side].length; i++) {
      var candidate = piece.connections[side][i];
      if (!candidate.alg_alignedMarked && color == candidate.color
           && Board.prototype.aligned(candidate, piece)) {
        candidate.swap();
        var canBeCaptured =  board.isPieceCaptured(candidate, OPPOSITE_COLOR[candidate.color]);
        candidate.swap();
        if (!canBeCaptured) {
          Algorithm.prototype._createLink(candidate, piece, side, index);
          this._findAllAlignedSwappablePiecesRec(board, candidate, color, index, out);
        } else {
          var can = true;
        }
      }
    }
  }
}

Algorithm.prototype._findImmediateSourcesToSplit = function(board, piece, index) {
  var color = OPPOSITE_COLOR[piece.color];
  var aligned = new Array();
  for (var side = 0; side < 4; side++) {
    for (var i = 0; i < piece.connections[side].length; i++) {
      var candidate = piece.connections[side][i];
      if (color == candidate.color) {
        var goodCandidate = false;
        if (Board.prototype.aligned(piece, candidate) && candidate.canSplit(DIR[side])) {
          goodCandidate = true;
          Algorithm.prototype._createLinkForSplit(candidate, piece, side, index, DIR[side]);
        } else if (piece.length[DIR[side]].twice().equals(candidate.length[DIR[side]]) &&
          		   candidate.canSplit(OPPOSITE_DIR[DIR[side]])) {

          // if candidate needs to be split in order to be aligned
          goodCandidate = true;
          Algorithm.prototype._createLinkForSplit(candidate, piece, side, index, OPPOSITE_DIR[DIR[side]]);
        }
        if (goodCandidate && !this._isSwapCaptured(board, candidate, index)) {
          aligned.push(candidate);
        }
      }
    }
  }
  return aligned;
}

Algorithm.prototype._findImmediateSourcesToMerge = function(board, piece, index) {
  var color = OPPOSITE_COLOR[piece.color];
  var aligned = new Array();
  for (var side = 0; side < 4; side++) {
    for (var i = 0; i < piece.connections[side].length; i++) {
      var candidate = piece.connections[side][i];
      if (color == candidate.color) {
        var goodCandidate = false;
        if (Board.prototype.aligned(piece, candidate) && candidate.connections[side].length == 1) {
            var sources = Algorithm.prototype._generateSourcesForMerge(candidate, side);
            if (sources && board.canMerge(sources[0], sources[1], sources[2], sources[3])) {
        	  goodCandidate = true;
              Algorithm.prototype._createLinkForMerge(candidate, piece, side, index, side);
            }
        } else if (candidate.length[DIR[side]].twice().equals(piece.length[DIR[side]])) {
           // if candidate needs to be merged in order to be aligned
           for (var t = 0; t < 2; t++) {
              var sources = Algorithm.prototype._generateSourcesForMerge(candidate, ALL_ORTHOGONAL_SIDES[side][t]);
              if (sources &&
                  (sources[0].start[HORIZONTAL].equals(piece.start[HORIZONTAL]) ||
                  sources[1].start[VERTICAL].equals(piece.start[VERTICAL])) &&
                  board.canMerge(sources[0], sources[1], sources[2], sources[3])) {
                goodCandidate = true;
                Algorithm.prototype._createLinkForMerge(candidate, piece, side, index, ALL_ORTHOGONAL_SIDES[side][t]);
                break;
              }
           }
        }
        if (goodCandidate && !this._isSwapCaptured(board, candidate, index)) {
          aligned.push(candidate);
        }
      }
    }
  }
  return aligned;
}

Algorithm.prototype._generateSourcesForMerge = function(first, side) {
    if (first.connections[side].length == 0) {
      return null;
    }
    var second = first.connections[side][0];
    if (first.color != second.color) {
      return null;
    }
    if (side == LEFT) {
      return [second, first, second, first];
    } else if ( side == RIGHT) {
      return [first, second, first, second];
    } else if (side == TOP) {
      return [second, second, first, first];
	} else { // BOTTOM
	  return [first, first, second, second];
	}
}

Algorithm.prototype._isSwapCaptured = function(board, candidate, index) {
  var captured = false;
  candidate.swap();
  var link = candidate.alg_link[index];
  var next = candidate.connections[link.side][link.id];
  next.swap();
  if (board.isPieceCaptured(next, OPPOSITE_COLOR[next.color])) {
    captured = true;
  }
  // swap back
  candidate.swap();
  next.swap();
  return captured;
}

Algorithm.prototype._createLinkAndAjust = function(board, newPiece, origPiece, index) {
  newPiece.alg_link = new Array();
  newPiece.alg_link[index] = new Link(origPiece.alg_link[index].side,
  	origPiece.alg_link[index].id, origPiece.alg_link[index].splitDir);
  // modify index in the list of connections
  var next  = board.equivalent(origPiece.connections[origPiece.alg_link[index].side][origPiece.alg_link[index].id]);
  newPiece.alg_link[index].id = -1;
  for (var c = 0; c < newPiece.connections[newPiece.alg_link[index].side].length; c++) {
    var neighbor  = newPiece.connections[newPiece.alg_link[index].side][c];
    if (neighbor == next) {
      newPiece.alg_link[index].id = c;
      break;
    }
  }
  assert(newPiece.alg_link[index].isValid());
}

Algorithm.prototype._createLinkAndAjustForMerge = function(board, newPiece, mergeSide, index) {
  newPiece.alg_link = new Array();
  newPiece.alg_link[index] = new Link(mergeSide, 0);
  // modify index in the list of connections
  var next  = newPiece.connections[mergeSide][0];
  assert(newPiece.alg_link[index].isValid());
}



Algorithm.prototype._createLink = function(src, dest, srcSide, index) {
  if (src.alg_link == undefined) {
    src.alg_link = new Array();
  }
  src.alg_link[index] = new Link(OPPOSITE_SIDE[srcSide]);
  // initialize the way to reach the next piece in a chain
  for (var j = 0; j < src.connections[OPPOSITE_SIDE[srcSide]].length; j++) {
    if (src.connections[OPPOSITE_SIDE[srcSide]][j] == dest) {
      src.alg_link[index].id = j;
      break;
    }
  }
  assert(src.alg_link[index].isValid());
}

Algorithm.prototype._createLinkForSplit = function(src, dest, srcSide, index, splitDir) {
  Algorithm.prototype._createLink(src, dest, srcSide, index);
  src.alg_link[index].splitDir = splitDir;
}

Algorithm.prototype._createLinkForMerge = function(src, dest, srcSide, index, mergeSide) {
  Algorithm.prototype._createLink(src, dest, srcSide, index);
  src.alg_link[index].mergeSide = mergeSide;
}


Algorithm.prototype._findSwappingSequence = function(start, end, i) {
  var swapped = new Array();
  swapped.push(start);
  var next = start;
  while (next != end) {
    if (next == null || next == undefined || next.alg_link == null || next.alg_link == undefined) {
      error;
    }
    var link = next.alg_link[i];
    var next = next.connections[link.side][link.id];
    swapped.push(next);
  }
  return swapped;
}

toTest.push(Algorithm);


Algorithm.prototype.test = function() {
    this.testCreateLink();
    this.testFindImmediateSources();
    this.testFindAllAlignedSwappablePieces();
    this.testEvaluate();
    this.testGetOpponentsImportantPieces();
    this.testGetWayToSwapPiece();
    this.testMakeMove();
}

Algorithm.prototype.testCreateLink = function() {
  alg = Algorithm.prototype._initTest(6, 6);
  alg._createLink(alg.board.pieces[1], alg.board.pieces[2], LEFT, 1, VERTICAL);
  var link = alg.board.pieces[1].alg_link[1];
  assert(link.id == 0);
  assert(link.splitDir == VERTICAL);
  assert(link.side == RIGHT);
}

Algorithm.prototype.testFindImmediateSources = function() {
  alg = Algorithm.prototype._initTest(6, 6);
  var i = 3;
  var j = 3;
  sources = alg._findImmediateSources(alg.board.pieces[i + j*6], 3);
  assert(sources.length == 4);
  var numVert = 0;
  var numHor = 0;
  var sides = [false, false, false, false];
  for (var s = 0; s < sources.length; s++) {
    var link = sources[s].alg_link[3];
    assert(link.id == 0);

    if (link.splitDir == VERTICAL) {
      numVert += 1;
    } else if (link.splitDir == HORIZONTAL) {
      numHor += 1;
    }
    sides[link.side] = true;
  }
  assert(numVert == 2);
  assert(numHor == 2);
  assert(sides[0] == true && sides[1] == true && sides[2] == true && sides[3] == true);
}

Algorithm.prototype.testFindAllAlignedSwappablePieces = function() {
  alg = Algorithm.prototype._initTest(6, 6);
  var i = 4;
  var j = 3
  var piece = alg.board.pieces[i + j*6];
  piece.swap();
  alg.board.pieces[i-2 + j*6].swap();
  var out = new Array();
  alg._findAllAlignedSwappablePiecesRec(piece, piece.color, 5, out);
  //   X X
  //  XXXXX
  //   X X
  assert(out.length == 9);
  return alg;
}

Algorithm.prototype.testGetOpponentsImportantPieces = function() {
  alg = Algorithm.prototype._initTest(3, 3);
  alg.board.pieces[6].swap();
  alg.board.pieces[7].swap();
  alg.board.pieces[8].swap();
  alg.move.color = alg.board.pieces[0].color;
  //  x[O]x
  //  0 x 0
  //  0 x 0
  var pieces = alg._getOpponentsImportantPieces();
  assert(pieces.length == 5);
  assert(pieces[0].start[HORIZONTAL].equals(ONE));
  assert(pieces[0].start[VERTICAL].equals(ZERO));
}

Algorithm.prototype.testEvaluate = function() {
  alg = Algorithm.prototype._initTest(3, 3);
  alg.board.pieces[6].swap();
  alg.board.pieces[7].swap();
  alg.board.pieces[8].swap();
  //  x[O]x
  //  0 x 0
  //  0 x 0
  alg._evaluate(alg.board, WHITE);
  alg.board.pieces.sort(this._byValue);
  assert(alg.board.pieces[0].start[HORIZONTAL].equals(ONE));
  assert(alg.board.pieces[0].start[VERTICAL].equals(ZERO));
  return alg;
}

Algorithm.prototype.testGetWayToSwapPiece = function() {  // x 0 x 0
  // 0 ||O x
  // 0 0 x 0
  // x x x 0
  alg = Algorithm.prototype._initTest(4, 4);
  alg.board.pieces[8].swap();
  alg.board.pieces[12].swap();
  alg.board.pieces[14].swap();
  alg.board.pieces[15].swap();
  alg.move.color = OPPOSITE_COLOR[alg.board.pieces[6].color];
  var way = alg._getWayToSwapPiece(alg.board.pieces[6], 3);
  assert(way.piece == alg.board.pieces[6]);
  assert(way.succeeded);
  assert(way.action == way.ACTION_SPLIT);
  assert(way.direction == VERTICAL);
  assert(way.sources.length == 1);
  assert(way.sources[0].start[HORIZONTAL].equals(ONE));
  assert(way.sources[0].start[VERTICAL].equals(ONE));
}


Algorithm.prototype.testMakeMove = function() {
  // x 0 x 0
  // 0 ||O x
  // 0 0 x 0
  // x x x 0
  alg = Algorithm.prototype._initTest(4, 4);
  alg.board.pieces[8].swap();
  alg.board.pieces[12].swap();
  alg.board.pieces[14].swap();
  alg.board.pieces[15].swap();
  alg.move.color = OPPOSITE_COLOR[alg.board.pieces[6].color];
  alg.makeMove();
  assert(alg.move.state == STATE_SPLIT);
  assert(alg.move.splitDir == VERTICAL);
  assert(alg.move.splitLine.equals(ONE.add(ONE.half())));
  assert(alg.move.swappedPieces[0].end[HORIZONTAL].equals(new Rational(2,1)));
  assert(alg.move.swappedPieces[0].end[VERTICAL].equals(new Rational(2,1)));
  assert(alg.move.numSwappedPieces == 2);
}

Algorithm.prototype._initTest = function(x, y) {
	var game = new Game(x, y, new Validator());
	var alg = new Algorithm(game.moves[game.getMoveId()]);
    return alg;
}